package solution;


import solution.bean.ListNode;

/*
* 206 链表
* */
public class ReverseList {

    /*
    * 普通思路
    * 迭代链表，使用第二个链表存储
    *
    * */
    public static ListNode sulution1(ListNode head) {
        //不能判断[1]这种情况
//        ListNode pre = null;
//        if (head != null && head.next != null) {
//            ListNode curr = head;
//            while (curr != null) {
//                ListNode next = curr.next;
//                curr.next = pre;
//                pre = curr;
//                curr = next;
//            }
//        }
//
//        return pre;


        //解决[1]的情况，少做几次循环
//        if (head != null) {
//            if (head.next != null){
//                ListNode pre = null;
//                ListNode curr = head;
//                while (curr != null) {
//                    ListNode next = curr.next;
//                    curr.next = pre;
//                    pre = curr;
//                    curr = next;
//                }
//                return pre;
//            }else {
//                return head;
//            }
//        }
//
//        return null;

        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /*
    * 使用递归
    * */
    public static ListNode solution2(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = solution2(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    /*
    * 使用双指针，双指针移动
    * */
    public static ListNode solution3(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    /*
    * 使用双指针，一个指针指向起点，另一个指针移动
    * */
    public static ListNode solution4(ListNode head){
        return head;
    }

    /*
    * 使用递归，好理解的递归
    * */
    public static ListNode pre = null;
    public static ListNode tmp = null;
    public static ListNode solution5(ListNode head){
        if (head == null){
            return pre;
        }
        tmp = head.next;
        head.next = pre;
        pre = head;
        head = tmp;
        return solution5(head);
    }

}
